#include<bits/stdc++.h>
#define int long long 
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while(ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while(ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while(x);
	while (__top) putchar(__stk[__top--] + '0');
}
bool stmer;
const int N = 1e5 + 10;
struct node {
    int x, l, r;
} op[N];
int n, q, k;
int a[N];
namespace sub1 {
    int cnt[N];
    unordered_map<int, int> mp[N];
    void update(int x) {
        int lat = a[x]; mp[x].clear(), cnt[x] = 0, mp[x][a[x]]++;
        for(int i = x + 1; i <= n; i++) if(a[i] > lat)
            cnt[x] += (mp[x][a[i]] ? 0 : 1), lat = a[i], mp[x][a[i]]++;
        lat = a[x];
        for(int i = x - 1; i; i--) if(a[i] > lat)
            cnt[x] += (mp[x][a[i]] ? 0 : 1), lat = a[i], mp[x][a[i]]++;
    }
    void solve() {
        for(int i = 1; i <= n; i++) update(i);
        for(int i = 1; i <= q; i++) {
            int x = op[i].x, l = op[i].l, r = op[i].r, ans = (r - l + 1) * (n - 1);
            swap(a[x], a[x + 1]), update(x), update(x + 1);
            // for(int i = 1; i <= n; i++) update(i);
            if(a[x] < a[x + 1]) {
                int mx = a[x - 1], val = a[x];
                for(int i = x - 1; i and mx < val; mx = max(mx, a[--i]))
                    cnt[i] += (mp[i][val] ? 0 : 1), mp[i][val]++;
                mx = a[x + 2];
                for(int i = x + 2; i <= n and mx < val; mx = max(mx, a[++i]))
                    mp[i][val]--, cnt[i] -= (mp[i][val] ? 0 : 1);
            }
            else if(a[x] > a[x + 1]) {
                int mx = a[x - 1], val = a[x + 1];
                for(int i = x - 1; i and mx < val; mx = max(mx, a[--i]))
                    mp[i][val]--, cnt[i] -= (mp[i][val] ? 0 : 1);
                mx = a[x + 2];
                for(int i = x + 2; i <= n and mx < val; mx = max(mx, a[++i]))
                    cnt[i] += (mp[i][val] ? 0 : 1), mp[i][val]++;
            }
            for(int i = l; i <= r; i++) ans += cnt[i] * k; write(ans), putchar('\n');
        }
    }
}
namespace sub2 {
    int top;
    int s[2][N], stk[N];
    bool check() {
        for(int i = 1; i <= q; i++) if(op[i].x ^ op[1].x) return 0;
        return 1;
    }
    void calc(int ty) {
        top = 0;
        for(int i = 1; i <= n; i++) {
            while(top and stk[top] <= a[i]) top--;
            s[ty][i] += top, stk[++top] = a[i];
        } top = 0;
        for(int i = n; i; i--) {
            while(top and stk[top] <= a[i]) top--;
            s[ty][i] += top, stk[++top] = a[i];
        }
        for(int i = 1; i <= n; i++) s[ty][i] += s[ty][i - 1];
    }
    void solve() {
        calc(0), swap(a[op[1].x], a[op[1].x + 1]), calc(1);
        for(int i = 1, ty = 0; i <= q; i++, ty ^= 1) {
            int l = op[i].l, r = op[i].r, ans = (r - l + 1) * (n - 1);
            ans += k * (s[ty][r] - s[ty][l - 1]), write(ans), putchar('\n');
        }
    }
}
bool edmer;
signed main() {
	freopen("summer.in", "r", stdin);
	freopen("summer.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
	n = read(), k = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    q = read();
    for(int i = 1; i <= q; i++) op[i] = {read(), read(), read()};
    if(n <= 1e3 and q <= 1e3) sub1 :: solve();
    else if(sub2 :: check()) sub2 :: solve();
    else sub1 :: solve();
    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds";
	return 0;
} 